P3327 [SDOI2015]约数个数和

发布于 2020-09-12 | 分类于莫比乌斯反演 | 5分钟 | 744字数

首先有一个公式：

d(ij)=\sum_{x|i}\sum_{y|j}[(i,j)=1]

CF464D World of Darkraft - 2

发布于 2020-09-12 | 分类于概率dp | 3分钟 | 497字数

首先明确一点，所有装备的期望相同，只需求出任意一种后答案乘 $k$ 即可。

令 $dp[i][j]$ 表示还需要打 $i$ 只怪，装备等级为 $j$ 的金币数量期望。

那么有三种情况：

发布于 2020-09-12 | 分类于概率dp | 5分钟 | 833字数

先考虑所有格子均未涂色的情况。

因为格子的涂色只会影响一行一列，所以可以设 $dp(i,j)$ 表示还需要涂 $i$ 行， $j$ 列的期望步数。

1.涂色格所在行列均未染色，由 $dp(i-1,j-1)$ 转移，概率为 $\frac{i}{n} \times \frac{j}{n}$

发布于 2020-09-12 | 分类于回文自动机 | 2分钟 | 296字数

看到求回文串就想到 $\text{PAM}$ 。

因为只有 $0,1$ 所以判断条件改成等于。

不过这道题满足题意的串长度一定为偶，所以不能走到 $-1$ 根。

发布于 2020-09-12 | 分类于数论 | 4分钟 | 516字数

\sum_{i=1}^n lcm(i,n)

\sum_{i=1}^n \frac{i*n}{gcd(i,n)}

发布于 2020-09-12 | 分类于莫比乌斯反演 | 5分钟 | 817字数

~~简单问题复杂化是解决问题的一个好方法。~~ 令

c_i

表示

i

出现的次数，

n

为最大数字。

\sum_{i=1}^n \sum_{j=1}^nc_i \times c_j \times lcm(i,j)

发布于 2020-09-12 | 分类于莫比乌斯反演 | 6分钟 | 983字数

\sum_{i=1}^n \sum_{j=1}^n (i+j)^k f(\gcd(i,j)) \gcd(i,j)

显然 $f(i)=\mu^2(i)$

发布于 2020-09-12 | 分类于莫比乌斯反演 | 9分钟 | 1353字数

\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^Cd(ijk)

\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C\sum_{x|i}\sum_{y|j}\sum_{z|k}[(x,y)=1][(y,z)=1][(x,z)=1]

发布于 2020-09-12 | 分类于莫比乌斯反演、伯努利数 | 11分钟 | 1781字数

如果不知道伯努利数的点这里。

\sum_{i=1}^n (i,n)^x[i,n]^y

发布于 2020-09-12 | 分类于莫比乌斯反演 | 5分钟 | 764字数

类比十进制下的纯循环小数， $k$ 进制下的纯循环小数满足最简分数分母与 $k$ 互质。

而题目要求相同数值只计数一次，所以只需要考虑最简分数的情况。

那么答案为：